package com.kobe.game_80;

import java.util.LinkedHashMap;
import java.util.Map;

public class Game78 {

    static Map<Integer, Integer> pDic = new LinkedHashMap<Integer, Integer>();

    static long p(int n) {
        if (n == 0) {
            return 1L;
        } else if (n < 0) {
            return 0L;
        }
        if (pDic.containsKey(n)) {
            return (long) pDic.get(n);
        }
        int k = 1;
        long count = 0L;
        while (true) {
            int n1 = n - (3 * k * k - k) / 2;
            int n2 = n - (3 * k * k + k) / 2;
            count = (count % 1000000 + (long) Math.pow(-1, k - 1)
                    * ((p(n1) % 10000000 + p(n2) % 10000000) % 10000000)) % 1000000;
            if (n2 <= 0) {
                pDic.put(n, (int) count);
                return (int) count;
            }
            k += 1;
        }
    }

    public static void main(String[] args) {
        int n = 2;
        while (true) {
            int pn = (int) p(n);
            if (n % 100 == 0) {
                //System.out.println(n);
            }
            if (pn == 0) {
                break;
            }
            //System.out.println(n + " : " + pn);
            n += 1;
        }
        System.out.println(n);
    }
}
